[集训队作业2018]-围绕着我们的圆环
$LOJ6040$ 加强版。高妙的线代题，虽然只用到了秩和线性空间的概念（完全不像今天国家队爷讲课那样让人摸不着头发哼！）
（接下来都用本题中的 $p$、$q$、$s$，这样比较严谨）
回顾矩阵乘法：$A(x, y) * B(y, z) \rightarrow C(x, z)$（绕晕了就看看这个👈）
考虑无修改怎么做，毫无头绪（
观察 $A$ 和 $C$ 的关系：$C$ 的列向量一定在 $A$ 列向量组成的线性空间里。
设 $A$ 的（列）秩为 $x$，$C$ 的（列）秩为 $r$。对于 $B$ 的每一列都可以列出一个有 $x$ 个线性无关的方程的方程组，那么自由元有 $q - x$ 个，一列的方案数是 $2^{q - x}$。因此在 $A$ 和 $C$ 的秩确定时，$B$ 方案数就是 $(2^{q - x})^s$。
现在我们要统计“秩为 $x$ 且列向量的线性空间包含 $C$ 的 $A$ 方案数”。这不好算。
dp, $f_{i, j}$ 表示 $i * q$ 的矩阵，秩为 $j$ 的方案数，转移类似线性基 dp。统计“秩为 $x$ 且列向量的线性空间包含秩为 $r$ 的 $C$ 的 $A$ 方案数”，最后答案除以 $g_{p, r}$。那么 $A$ 的方案数就是 $f_{q, x}$，$C$ 的方案数就是 $g_{x, r}$，为什么？
因为行秩 = 列秩，$C$ 中对应 $A$ 的那 $x$ 行确定后剩下的行就像 $A$ 中剩下的行那样能被那 $x$ 行表出的。
答案就是 $\sum\limits_{x = r}^q f_{q, x} g_{x, r} (2^{q - x})^s$
本题要我们动态求矩阵的秩。
大概就是个线性基状物的插入和删除。删除怎么搞？大佬比较详细的解说 考虑删除向量 $x$ 后我们要尽量找一个来替代 $x$。对线性基里每个向量记录它插入时异或了哪些向量。找到「受本次删除影响」的基外向量 $y$，如果不存在基外的就找基内最低的（这样在删除时就不会影响更低位的向量），把 $y$ 其它受影响的向量异或上 $y$（$y$ 自己变成 $0$，这样就能消除 $x$ 在线性基里的影响，相当于用 $y$ 替代了 $x$）；如果找的是基内的，秩数 $-1$。
用 bitset，$O(\frac{n^3}{\omega})$